public class MyLinkedList implements IList {
    //结点类
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


    public ListNode head;
    public ListNode tail;

    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        if(head == null) {
            head = tail = newNode;
            return;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        if(head == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    @Override
    public void addIndex(int index, int data) {
        if(index < 0 || index > size()) {
            throw new IllegalIndexException("Illegal Index !: 下标非法！");
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode newNode = new ListNode(data);
        int count = 1;
        ListNode cur = this.head.next;
        while(cur != null) {
            if(count == index) {
                cur.prev.next = newNode;
                newNode.next = cur;
                newNode.prev = cur.prev;
                cur.prev = newNode;
                return;
            }
            count++;
            cur = cur.next;
        }
    }

    @Override
    public boolean contains(int key) {
        if(head == null) {
            return false;
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head == null) {
            throw new ListIsEmptyException("List Is Empty !: 链表为空!");
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    head = head.next;
                    if(cur.next == null) {
                        head = tail = null;
                    }else {
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if (cur == tail) {
                        tail = cur.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                    return;
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        if(head == null) {
            throw new ListIsEmptyException("List Is Empty !: 链表为空!");
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    head = head.next;
                    if(cur.next == null) {
                        head = tail = null;
                    }else {
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if (cur == tail) {
                        tail = cur.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {
        ListNode cur = head;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curN;
        }
        tail = head = null;
    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

class TestMyLinkedList {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(2);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(3);
//        myLinkedList.addLast(1);
//        myLinkedList.addLast(0);
//        myLinkedList.addLast(1);
        myLinkedList.display();
        myLinkedList.removeAllKey(2);
        myLinkedList.addIndex(3,2);
        myLinkedList.display();
    }
}
